\chapter{Optimisations multicoeurs}

\section{Problématiques multicoeurs et solutions connues}

Trois principaux goulots d'étranglement ont été identifiés précédemment : la \emph{capacité du cache L3}, la \emph{bande passante off-chip}, et les \emph{défauts de page mémoire}.

Deux principales catégories d'optimisations permettent de répondre à ces problématiques : les optimisations \emph{algorithmiques} et les optimisations locales de \emph{code source}. 
Les optimisations algorithmiques consistent à augmenter l'intensité arithmétique et à réduire la contention. Elle requiert un bon niveau de connaissance de l'algorithme afin de l'améliorer. C'est une optimisation difficile et non portable. 
La seconde par contre, nécessite peu de connaissances au sujet du code à optimiser, elle est typiquement locale aux nids de boucles et facile à mettre en place. Elle peut même être automatiquement appliquée par un compilateur. C'est donc à ce type d'optimisation que s'intéresse l'article.

\section{Microfission de boucles}

\subsection{Principe}
La \emph{microfission de boucles} est une spécialisation d'optimisations bien connues : la \emph{fission de boucles} et la \emph{fusion de boucles}. La fusion de boucle consiste à regrouper en une seule boucle deux boucles travaillant sur le même espace d'itérations. La fission est l'opération inverse qui consiste à éclater une boucle en plusieurs boucles plus petites.
L'opération consiste à transformer une boucle complexe en plusieurs boucles simples et est effectuée en deux étapes :
\begin{enumerate}
	\item Fission de la boucle complexe en plusieurs boucles simples, en respectant les critères suivants : pas plus de deux tableaux, dont un chargement par nid de boucle.En somme, respect du \textit{pattern} suivant, $C[i]=f(C[i],X[i])$, où C[i] est stocké dans le cache et X[i] est chargé.
	\item Fusion, lorsque cela est possible, des boucles opérants sur les mêmes tableaux
\end{enumerate}

\subsection{Exemple}

La figure \ref{nid} montre une boucle complexe constituée de 3 boucles imbriquées. Le nid de boucle accède à trois tableaux distincts suivant vingt séquences différentes. 

\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=12cm]{images/nid_boucles}
		\caption{Nid de boucle complexe (extrait de code de la boucle PreqRobert)}
		\label{nid}
	\end{center}
\end{figure}

La figure \ref{microfission} présente le code obtenu après application de la microfission sur la première ligne du nid de boucles. Un tableau est chargé dans le cache, et y reste. Les autres, un seul tableau par boucle, sont chargés au fur et à mesure.
Cette méthode a l'avantage d'une part, de réduire les \textit{cache-miss} L3 et d'autre part d'éviter les accès dispersés et les défauts de page mémoire. De plus, les boucles étant de plus petite tailles, le compilateur peut appliquer des optimisations. Enfin, le contrôleur mémoire peut également mieux gérer les requêtes, et les grouper par lots.

\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=12cm]{images/microfission_exemple}
		\caption{Microfission de la 1ère ligne}
		\label{microfission}
	\end{center}
\end{figure}

Un des risques de cette méthode est de voir l'optimisation détruite par le compilateur qui effectuerait des fusions de boucles.A défaut de pouvoir spécifier au compilateur de ne effectuer de fusion sur ces boucles, il faut alors encapsuler dans des fonctions. Malgré ces encapsulations, les résultats restent très bons.

\subsection{Résultats}

La figure \ref{micro_res} montre les résultats obtenus lors de l'application de la microfission sur la fonction PreqRobert du benchmark HOMME à l'exécution sur le \textit{cluster} Ranger.

\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=10cm]{images/microfission_res}
		\caption{Résultats de l'application de la microfission}
		\label{micro_res}
	\end{center}
\end{figure}

La performance globale a augmenté de 33\% sur Ranger et 35\% sur Longhorn. Le taux de \textit{miss} L2 n'est quasiment pas impacté : cela montre que la microfission est une optimisation multicoeur qui a très peu d'effets sur les coeurs individuels. Les taux de miss L3 et de \textit{page miss} diminuent de moitié. La contention \textit{on-chip}, pour la L3 partagée, et \textit{off-chip}, pour la DRAM sont donc diminuées.

La microfission a aussi des effets bénéfiques sur la scalabilité \textit{intranode}. L'efficacité, à 4 coeurs par processeur, atteint 78\% sur Ranger et 58\% sur Longhorn.

\subsection{Recommandations de codage}
\noindent Les résultats de cette optimisation suggèrent des lignes directrices pour le développement d'application HPC régulières :
\begin{itemize}
	\item Utiliser des structures de tableaux (\textit{Structures Of Arrays SOA}), plutôt que tableaux de structures (\textit{Arrays Of Structures AOS}).
	\item Regrouper le plus de calcul possible dans une même boucle. (Faire augmenter l'intensité arithmétique). 
	\item Minimiser le nombre de tableaux temporaires.
	\item Ajuster la tailles des blocs pour qu'ils puissent tenir en cache.
\end{itemize}
